package com.cqs.leetcode.math;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * lixw
 * 2021/11/2
 **/
public class DuplicateNumber287 {

    /**
     *   将nums看作指针， 其中nums[i] 表示next
     */
    public int findDuplicate(int[] nums) {
        int fast = 0, slow = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while (fast != slow);

        slow = 0;
        while (slow != fast) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }

    public static void main(String[] args) {
        List<int[]> cases = new ArrayList<>();
        cases.add(new int[]{4,3,1,4,2});
        cases.add(new int[]{1,2,3,4,4});
        cases.add(new int[]{1,4,3,4,2});
        cases.add(new int[]{1,3,4,2,2});
        cases.add(new int[]{3,1,3,4,2});
        cases.add(new int[]{1,1});
        cases.add(new int[]{1,1});
        DuplicateNumber287 d = new DuplicateNumber287();
        for (int[] c: cases) {
            System.out.println(ArraysUtils.formatInts(c) + "---->" + d.findDuplicate(c));
        }
    }
}
